#include <stdio.h>
#include <stdlib.h>
#include <time.h>

double expon(double *, float);

#define NJOB 3		//The number of customers per run
#define EXPARRI 2.0		//The expected customer interarrival time
#define EXPSERVICE 1.0		//The expected service time
#define INFINITE 100000000	//Indicate a very large value
#define IDLE 0
#define BUSY 1
#define NMAX 2000			//Number of queues in a tandem queue

double seed = 7654321;
double arrive[NJOB];

double runtime[NMAX];			//record the runtime for each N

int i[NMAX];				//current customer being served
int j[NMAX];				//next customer to arrive
double servstatus[NMAX];	//status of each server
double nextarrive[NMAX];	//next arrival event for each server
double nextdepart[NMAX];	//next departure event for each server
int queuelen[NMAX];		//queue length of each server
int finish;			//record #jobs that have finished all services

int isarrive;			//earlest event is arrive or not
int earliestqueue;		//in which queue the earliest event occurs
double earliesttime;		//the time of the earliest event

//Time of arrival to the first queue of each job
void init(void)
{
	int k;
	arrive[0] = expon(&seed,EXPARRI);
	for(k=1; k<NJOB; k++)
	{
		arrive[k] = arrive[k-1] + expon(&seed,EXPARRI);
	}
}

void earliest(int N)
{
	double min;
	int e;
	earliestqueue = 0;
	min = nextarrive[earliestqueue];	
	isarrive = 1;
	for(e = 0; e < N; e ++)
	{
		if(nextarrive[e] < min)
		{
			min = nextarrive[e];
			isarrive = 1;
			earliestqueue = e;
		}
		if(nextdepart[e] < min)
		{
			min = nextdepart[e];
			isarrive = 0;
			earliestqueue = e;
		}
	}
	earliesttime = min;
}

void arrive_handler(int n, double time)
{
	time = time;
	//printf(" Time%5.1f: Job %d arrives at server %d\r\n", time, j[n], n);
	j[n] ++;
	if(servstatus[n] == IDLE)
	{
		servstatus[n] = BUSY;
		//printf(" Time%5.1f: Job %d starts to get service at server %d\r\n", time, j[n]-1, n);
		nextdepart[n] = time + expon(&seed,EXPSERVICE);
	}
	else
	{
		queuelen[n] = queuelen[n] + 1;
		//printf(" Time%5.1f: Job %d gets in queue %d which now has %d people\r\n", time, j[n]-1, n, queuelen[n]);
	}
	if((n == 0) && (j[n] < NJOB))
		nextarrive[n] = arrive[j[n]];
	else if ((n != 0) && (j[n] < NJOB))
		nextarrive[n] = nextdepart[n-1] + 0.1;
	else
		nextarrive[n] = INFINITE;
}

void depart_handler(int n, double time, int N)
{
	//printf(" Time%5.1f: Job %d departs from server %d\r\n", time, i[n], n);
	i[n] ++;
	if (queuelen[n] == 0)
	{
		servstatus[n] = IDLE;
		//printf(" Time%5.1f: Server %d status starts to be IDLE\r\n", time, n);
		nextdepart[n] = INFINITE;
	}
	else
	{
		queuelen[n] --;
		servstatus[n] = BUSY;
		//printf(" Time%5.1f: Job %d leaves queue %d to start service which now has %d people\r\n",time, i[n], n, queuelen[n]);
		nextdepart[n] = time + expon(&seed,EXPSERVICE);
	}
	if(n+1 < N)
		nextarrive[n+1] = time + 0.1;
	else
	{
		//printf(" Time%5.1f: Job %d has finished all services\r\n", time, i[n] - 1);
	}
}


int main(void)
{
	//Initialize the run time
	int qamount;
	int s, d, k;
	struct timeval time_start,  time_stop ;
    double time_pass;
 
	for(qamount = 1; qamount*100 < NMAX; qamount ++)
	{
		//printf("\r\nWhen N = %d:\r\n", qamount);
		runtime[qamount*100] = 0;
		gettimeofday(&time_start, NULL);
		//Initialization
		for(s = 0; s < qamount*100; s++)
		{
			i[s] = 0;
			j[s] = 0;
			servstatus[s] = IDLE;
			nextarrive[s] = INFINITE;
			nextdepart[s] = INFINITE;
			queuelen[s] = 0;
		}
		finish = 0;
		init();
		nextarrive[0] = arrive[0];
		while(finish < NJOB*2*qamount*100)
		{
			earliest(qamount);
			if(isarrive)
			{
				arrive_handler(earliestqueue, earliesttime);
			}
			else
			{
				depart_handler(earliestqueue, earliesttime, qamount*100);
			}
			finish ++;
		}
		gettimeofday(&time_stop, NULL);
		runtime[qamount*100] = time_pass = ((double)time_stop.tv_sec -(double)time_start.tv_sec)*1000000 + (double)time_stop.tv_usec-(double)time_start.tv_usec;
	}
	printf("\r\nN vs. run time (one '*' = 0.2 msec)");
	for (d=1; d*100<NMAX; d++){
		printf("\nN=%5d |",d*100);
		for (k=0; k*200 < runtime[d*100]; k++)
			printf("*");
	}

	printf("\r\n\r\n");
}
